package leetcode每日一题;

import java.util.Arrays;

/**
 * 1. 问题描述
 *      给定两个字符串 s 和 t，它们只包含小写字母。
 *      字符串 t 由字符串 s 随机重排，然后在随机位置添加一个字母。
 *      请找出在 t 中被添加的字母。
 *
 * 2. 算法分析
 *
 *
 *
 * 3. 代码实现
 */
@SuppressWarnings("all")
public class 找不同 {
    public static void main(String[] args) {
        int a = 97;
        System.out.println((char) a);
        String s = "abc";
        System.out.println(s.indexOf('c'));
    }

    /**
     * 将s，t转化为字符数组，调用底层Arrays类中的sort方法，然后线性遍历即可
     * 时间复杂度O(2nlogn+n)  空间复杂度O(2n)
     * @param s
     * @param t
     * @return
     */
    public static char findTheDifference1(String s, String t) {
        if(s.length() == 0) {return t.charAt(0);} // 当s为空字符串时
        char[] chars = s.toCharArray();
        char[] chart = t.toCharArray();
        Arrays.sort(chars); Arrays.sort(chart);
        for(int i = 0; i < chars.length; i++) {
            if(chars[i] != chart[i]) {
                return chart[i];
            }
        }
        return chart[chart.length-1];
    }

    /**
     * 对上述的一个优化，采用hash来做，省去了调用底层的排序方法，控制在线性时间内
     * 空间上优化到常数
     * @param s
     * @param t
     * @return
     */
    public static char findTheDifference2(String s, String t) {
        if(s.length() == 0) {return t.charAt(0);} // 当s为空字符串时
        int[] count1 = new int[26]; // 计数器 s
        int[] count2 = new int[26]; // 计数器 t
        for(int i = 0; i < s.length(); i++) {
            count1[s.charAt(i)-'a']++; // 计数
        }
        for(int i = 0; i < t.length(); i++) {
            count2[t.charAt(i)-'a']++;
        }
        for(char ch : t.toCharArray()) {
            if(count1[ch-'a'] == 0) {
                return ch;
            } else {
                count1[ch-'a']--;
            }
        }
        return '*';
    }

    /**
     * 对2的进一步优化，上述实际上采用了两个hash，这里我们只使用一个hash来实现对两个字符串的比较
     * @param s
     * @param t
     * @return
     */
    public static char findTheDifference3(String s, String t) {
        if(s.length() == 0) {return t.charAt(0);}
        int[] count = new int[26];
        for(int i = 0; i < s.length(); i++) {
            count[s.charAt(i) - 'a']++;
        }
        for(int i = 0; i < t.length(); i++) {
            count[t.charAt(i) - 'a']--;
        }
        for(int i = 0; i < count.length; i++) {
            if(count[i] != 0) {
                return (char) (i + 'a');
            }
        }
        return ' ';
    }

    /**
     * 计算两个字符串的字符的和，只差就是新的字符的asll值，通过char转型即可
     * 时间为O(n) 空间O(1)
     * @param s
     * @param t
     * @return
     */
    public static char findTheDifference4(String s,String t) {
        int temp1 = 0; int temp2 = 0;
        for(char ch : s.toCharArray()) {
            temp1 += ch;
        }
        for(char ch : t.toCharArray()) {
            temp2 += ch;
        }
        return (char) (temp2-temp1);
    }

    /**
     * 使用位运算  此题实际上是之前leetcde上的题目的变式题 136 查找只出现一次的元素
     * 136：一个数组中只有一个元素出现了一次，其余的元素都出现了两次，我们采用位运算^
     * 根据位运算的性质：a ^ a = 0  a ^ b = b ^ a
     *
     * 对于此题而言实际上根据题意可知，与上述问题是一样的，位运算在进行数字运算时比普通的加减乘除快
     * 因为计算机底层就是进制，所以相当于机器码，不需要转换
     * @param s
     * @param t
     * @return
     */
    public static char findTheDifference5(String s,String t) {
        int ret = 0;
        for(char ch : s.toCharArray()) {
            ret ^= ch;
        }
        for(char ch : t.toCharArray()) {
            ret ^= ch;
        }
        return (char) ret;
    }


}
